package newcoder.JZ71;

import java.util.ArrayList;
import java.util.List;

//1,2,3,4,5,6,7
//1,2,3,10,21,42
public class Solution {

    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<ArrayList<Integer>> arrayLists = solution.FindContinuousSequence(9);
        arrayLists.forEach(list->{
            System.out.println(list);
        });
    }

    public static int jumpFloorII(int target) {
        int[] d= new int[target+1];
        d[1] = 1;
        for (int i = 2; i <= target ; i++) {
            for (int j = 1; j < i ; j++) {
                d[i]+=d[j];
            }
            d[i]+=1;
        }
        return d[target];
    }

    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        for (int i = 1; i < sum ; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            back(list,i,i+1,sum);
        }
        return result;
    }

    public void back(ArrayList<Integer> list,int sum, int current,int target){
        if (sum==target){
            result.add(list);
            return;
        }
        if (sum+current>target){
            return;
        }
        sum = sum+current;
        list.add(current);
        back(list,sum,current+1,target);
    }
}
